package src.algorithm;

/**
 * 本类主要研究常用的排序算法，有冒泡排序，选择排序，折半排序等，
 * 稳定：冒泡排序、插入排序、归并排序和基数排序
 * 不稳定：选择排序、快速排序、希尔排序、堆排序
 * 1、输入数字选择排序的方法，2、输入几个数字，回车执行
 */
public class SortingAlgorithm
{
    public static void main(String[] args)
    {
/*        System.out.println("请输入下面算法的对应数字选择对应算法：");
        System.out.println("1.冒泡排序，2.插入排序，3.选择排序，4.快速排序，5基数排序，6.归并排序");
        Scanner scanner = new Scanner(System.in);
        String selectSort = scanner.next();*/

        int[] a = new int[]{2,7,4,5,10,1,9,3,8,6};
        int[] b = new int[]{1,2,3,4,5,6,7,8,9,10};
        int[] c = new int[]{10,9,8,7,6,5,4,3,2,1};
        int[] d = new int[]{1,10,2,9,3,2,4,7,5,6};

        sort(a, 0, a.length-1);

        System.out.println("排序后的结果：");
        for(int x : a){
            System.out.print(x+" ");
        }


        //int[] intList = {2,4,1,3,8,7,9,5,6,10,13,12,11};
        //intList = SortingAlgorithm.BubbleSort(intList);
    }

    /**
     * 冒泡排序，两组循环，两两比较两个数的大小（比如；1和2比较，2和3比较），根据条件交换位置，不交换的条件是：前一个数小于或大于后一个数
     * 优化：添加一个end标识用来提前结束循环
     * @param intList
     * @return
     */
    public static int[] BubbleSort(int[] intList)
    {
        System.out.print("排序前：");
        for (int num:intList)
            System.out.print(num+",");
        System.out.println("\n排序中：");
        int temp = 0;
        int count = 0;
        Boolean end = true;//排序结束标识
        for(int i=0;i<intList.length-1;i++)//外层循环控制排序趟数
        {
            end = true;
            for(int j=0;j<intList.length-1-i;j++)//内层循环控制每一趟排序多少次
            {
                if(intList[j]>intList[j+1])
                {
                    count++;
                    end = false;
                    temp=intList[j];
                    intList[j]=intList[j+1];
                    intList[j+1]=temp;
                }
            }
            if(end)
            {
                System.out.println("一共交换："+count+"次,\n排序后：");
                for (int num:intList)
                    System.out.print(num+",");
                return intList;
            }
            System.out.print("第"+(i+1)+"次：");
            for (int num:intList)
                System.out.print(num+",");
            System.out.println();
        }
        System.out.println("一共交换："+count+"次,\n排序后：");
        for (int num:intList)
            System.out.print(num+",");
        return intList;
    }

    /**
     * 选择排序
     */
    public static int[] SelectSort(int[] intList)
    {
        return intList;
    }

    /**
     * 快速排序
     */
    public static int[] QueklySort(int[] intList)
    {
        //
        return intList;
    }

    /**
     * 将数组的某一段元素进行划分，小的在左边，大的在右边
     * divide 分配
     * @param a
     * @param start
     * @param end
     * @return
     */
    public static int divide(int[] a, int start, int end)
    {
        //每次都以最右边的元素作为基准值
        int base = a[end];
        //start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。
        while(start < end){
            while(start < end && a[start] <= base)
                //从左边开始遍历，如果比基准值小，就继续向右走
                start++;
            //上面的while循环结束时，就说明当前的a[start]的值比基准值大，应与基准值进行交换
            if(start < end){
                //交换
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
                //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值右边)，因此右边也要同时向前移动一位
                end--;
            }
            while(start < end && a[end] >= base)
                //从右边开始遍历，如果比基准值大，就继续向左走
                end--;
            //上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换
            if(start < end){
                //交换
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
                //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位
                start++;
            }
        }
        //这里返回start或者end皆可，此时的start和end都为基准值所在的位置
        return end;
    }

    /**
     * 排序
     * @param a
     * @param start
     * @param end
     */
    public static void sort(int[] a, int start, int end){
        if(start > end){
            //如果只有一个元素，就不用再排下去了
            return;
        }
        else{
            //如果不止一个元素，继续划分两边递归排序下去
            int partition = divide(a, start, end);
            sort(a, start, partition-1);//左边排序一次
            sort(a, partition+1, end); //右边排序一次
        }
    }

    /**
     * 对指定的数组中索引从start到end之间的元素进行快速排序
     *
     * @param array 指定的数组
     * @param start 需要快速排序的数组索引起点
     * @param end 需要快速排序的数组索引终点
     */
    public static final void quickSort(int[] array, int start, int end) {
        // i相当于助手1的位置，j相当于助手2的位置
        int i = start, j = end;
        int pivot = array[i]; // 取第1个元素为基准元素
        int emptyIndex = i; // 表示空位的位置索引，默认为被取出的基准元素的位置
        // 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
        while (i < j) {
            // 助手2开始从右向左一个个地查找小于基准元素的元素
            while (i < j && pivot <= array[j])
                j--;
            if (i < j) {
                // 如果助手2在遇到助手1之前就找到了对应的元素，就将该元素给助手1的"空位"，j成了空位
                array[emptyIndex] = array[emptyIndex = j];
            }

            // 助手1开始从左向右一个个地查找大于基准元素的元素
            while (i < j && array[i] <= pivot)
                i++;
            if (i < j) {
                // 如果助手1在遇到助手2之前就找到了对应的元素，就将该元素给助手2的"空位"，i成了空位
                array[emptyIndex] = array[emptyIndex = i];
            }
        }
        // 助手1和助手2相遇后会停止循环，将最初取出的基准值给最后的空位
        array[emptyIndex] = pivot;

        // =====本轮快速排序完成=====

        // 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
        if (i - start > 1) {
            quickSort(array, 0, i - 1);
        }
        // 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
        if (end - j > 1) {
            quickSort(array, j + 1, end);
        }
    }

    //主方法
    /*public static void main(String[] args) {
        // =====使用快速排序法对表示8名运动员身高的数组heights进行从低到高的排序=====
        // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
        int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 };
        // 调用快速排序方法
        quickSort(heights, 0, heights.length - 1);
        // 输出排序后的结果
        for (int height : heights) {
            System.out.println(height);
        }
    }*/


}
